<!DOCTYPE html>
<html lang="en" dir="auto">

<head><meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<meta name="robots" content="index, follow">
<title>算法 | Johnhoo&#39;s Blog</title>
<meta name="keywords" content="" />
<meta name="description" content="常见算法 线性表 滑动窗口 定义 在给定特定窗口大小的数组或字符串上执行要求的操作
示意图 特点 如果要计算窗口内值得和：每次向右滑一格，只需要增加新格的值，然后减去窗口头的值即可，减少重复计算；
时间复杂度 由于只需要一次遍历就可以取到窗口格中的数据，所以时间复杂度为数组长度O(n)
代码 def SlideWindow(nums: List[int], size: int): left = 0, right = 0 while(right &lt; len(nums)): right_num = nums[right]	# right_num为将要移入窗口的数值 right &#43;= 1	# 右窗口右移 ...	# 进行窗口内数据的一系列更新 while(window needs shrink):	# 判断左侧窗口是否要收缩 left_num = nums[left]	# left_num为将移出窗口的字符 left&#43;= 1	# 左窗口右移 ...	# 进行窗口内数据的一系列更新 题目 力扣1984：学生分数的最小差值
资料 https://labuladong.gitee.io/algo/2/21/60/
查找&amp;排序 二分查找 定义 数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。
特点 数组必须是按有序结构的；
时间复杂度 O(log2n)
时间复杂度即是while循环的次数。总共n个元素，每次分成2个子数组，每个子数组为n/2, n/4, &hellip;, n/2^k，k为循环次数">
<meta name="author" content="">
<link rel="canonical" href="http://johnhoowong.gitee.io/blog.gitee.io/posts/%E7%AE%97%E6%B3%95/" />
<link crossorigin="anonymous" href="/blog.gitee.io/assets/css/stylesheet.min.c88963fe2d79462000fd0fb1b3737783c32855d340583e4523343f8735c787f0.css" integrity="sha256-yIlj/i15RiAA/Q&#43;xs3N3g8MoVdNAWD5FIzQ/hzXHh/A=" rel="preload stylesheet" as="style">
<script defer crossorigin="anonymous" src="/blog.gitee.io/assets/js/highlight.min.7680afc38aa6b15ddf158a4f3780b7b1f7dde7e91d26f073e6229bb7a0793c92.js" integrity="sha256-doCvw4qmsV3fFYpPN4C3sffd5&#43;kdJvBz5iKbt6B5PJI="
    onload="hljs.initHighlightingOnLoad();"></script>
<link rel="icon" href="http://johnhoowong.gitee.io/blog.gitee.io/favicon.ico">
<link rel="icon" type="image/png" sizes="16x16" href="http://johnhoowong.gitee.io/blog.gitee.io/favicon-16x16.png">
<link rel="icon" type="image/png" sizes="32x32" href="http://johnhoowong.gitee.io/blog.gitee.io/favicon-32x32.png">
<link rel="apple-touch-icon" href="http://johnhoowong.gitee.io/blog.gitee.io/apple-touch-icon.png">
<link rel="mask-icon" href="http://johnhoowong.gitee.io/blog.gitee.io/safari-pinned-tab.svg">
<meta name="theme-color" content="#2e2e33">
<meta name="msapplication-TileColor" content="#2e2e33">
<meta name="generator" content="Hugo 0.85.0" />
<noscript>
    <style>
        #theme-toggle,
        .top-link {
            display: none;
        }

    </style>
    <style>
        @media (prefers-color-scheme: dark) {
            :root {
                --theme: rgb(29, 30, 32);
                --entry: rgb(46, 46, 51);
                --primary: rgb(218, 218, 219);
                --secondary: rgb(155, 156, 157);
                --tertiary: rgb(65, 66, 68);
                --content: rgb(196, 196, 197);
                --hljs-bg: rgb(46, 46, 51);
                --code-bg: rgb(55, 56, 62);
                --border: rgb(51, 51, 51);
            }

            .list {
                background: var(--theme);
            }

            .list:not(.dark)::-webkit-scrollbar-track {
                background: 0 0;
            }

            .list:not(.dark)::-webkit-scrollbar-thumb {
                border-color: var(--theme);
            }
        }

    </style>
</noscript><meta property="og:title" content="算法" />
<meta property="og:description" content="常见算法 线性表 滑动窗口 定义 在给定特定窗口大小的数组或字符串上执行要求的操作
示意图 特点 如果要计算窗口内值得和：每次向右滑一格，只需要增加新格的值，然后减去窗口头的值即可，减少重复计算；
时间复杂度 由于只需要一次遍历就可以取到窗口格中的数据，所以时间复杂度为数组长度O(n)
代码 def SlideWindow(nums: List[int], size: int): left = 0, right = 0 while(right &lt; len(nums)): right_num = nums[right]	# right_num为将要移入窗口的数值 right &#43;= 1	# 右窗口右移 ...	# 进行窗口内数据的一系列更新 while(window needs shrink):	# 判断左侧窗口是否要收缩 left_num = nums[left]	# left_num为将移出窗口的字符 left&#43;= 1	# 左窗口右移 ...	# 进行窗口内数据的一系列更新 题目 力扣1984：学生分数的最小差值
资料 https://labuladong.gitee.io/algo/2/21/60/
查找&amp;排序 二分查找 定义 数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。
特点 数组必须是按有序结构的；
时间复杂度 O(log2n)
时间复杂度即是while循环的次数。总共n个元素，每次分成2个子数组，每个子数组为n/2, n/4, &hellip;, n/2^k，k为循环次数" />
<meta property="og:type" content="article" />
<meta property="og:url" content="http://johnhoowong.gitee.io/blog.gitee.io/posts/%E7%AE%97%E6%B3%95/" /><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-03-06T12:34:17&#43;08:00" />
<meta property="article:modified_time" content="2022-03-06T12:34:17&#43;08:00" />

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="算法"/>
<meta name="twitter:description" content="常见算法 线性表 滑动窗口 定义 在给定特定窗口大小的数组或字符串上执行要求的操作
示意图 特点 如果要计算窗口内值得和：每次向右滑一格，只需要增加新格的值，然后减去窗口头的值即可，减少重复计算；
时间复杂度 由于只需要一次遍历就可以取到窗口格中的数据，所以时间复杂度为数组长度O(n)
代码 def SlideWindow(nums: List[int], size: int): left = 0, right = 0 while(right &lt; len(nums)): right_num = nums[right]	# right_num为将要移入窗口的数值 right &#43;= 1	# 右窗口右移 ...	# 进行窗口内数据的一系列更新 while(window needs shrink):	# 判断左侧窗口是否要收缩 left_num = nums[left]	# left_num为将移出窗口的字符 left&#43;= 1	# 左窗口右移 ...	# 进行窗口内数据的一系列更新 题目 力扣1984：学生分数的最小差值
资料 https://labuladong.gitee.io/algo/2/21/60/
查找&amp;排序 二分查找 定义 数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。
特点 数组必须是按有序结构的；
时间复杂度 O(log2n)
时间复杂度即是while循环的次数。总共n个元素，每次分成2个子数组，每个子数组为n/2, n/4, &hellip;, n/2^k，k为循环次数"/>


<script type="application/ld+json">
{
  "@context": "https://schema.org",
  "@type": "BreadcrumbList",
  "itemListElement": [, 
    {
      "@type": "ListItem",
      "position":  2 ,
      "name": "Posts",
      "item": "http://johnhoowong.gitee.io/blog.gitee.io/posts/"
    }, 
    {
      "@type": "ListItem",
      "position":  3 ,
      "name": "算法",
      "item": "http://johnhoowong.gitee.io/blog.gitee.io/posts/%E7%AE%97%E6%B3%95/"
    }
  ]
}
</script>
<script type="application/ld+json">
{
  "@context": "https://schema.org",
  "@type": "BlogPosting",
  "headline": "算法",
  "name": "算法",
  "description": "常见算法 线性表 滑动窗口 定义 在给定特定窗口大小的数组或字符串上执行要求的操作\n示意图 特点 如果要计算窗口内值得和：每次向右滑一格，只需要增加新格的值，然后减去窗口头的值即可，减少重复计算；\n时间复杂度 由于只需要一次遍历就可以取到窗口格中的数据，所以时间复杂度为数组长度O(n)\n代码 def SlideWindow(nums: List[int], size: int): left = 0, right = 0 while(right \u0026lt; len(nums)): right_num = nums[right]\t# right_num为将要移入窗口的数值 right += 1\t# 右窗口右移 ...\t# 进行窗口内数据的一系列更新 while(window needs shrink):\t# 判断左侧窗口是否要收缩 left_num = nums[left]\t# left_num为将移出窗口的字符 left+= 1\t# 左窗口右移 ...\t# 进行窗口内数据的一系列更新 题目 力扣1984：学生分数的最小差值\n资料 https://labuladong.gitee.io/algo/2/21/60/\n查找\u0026amp;排序 二分查找 定义 数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。\n特点 数组必须是按有序结构的；\n时间复杂度 O(log2n)\n时间复杂度即是while循环的次数。总共n个元素，每次分成2个子数组，每个子数组为n/2, n/4, \u0026hellip;, n/2^k，k为循环次数",
  "keywords": [
    
  ],
  "articleBody": "常见算法 线性表 滑动窗口 定义 在给定特定窗口大小的数组或字符串上执行要求的操作\n示意图 特点 如果要计算窗口内值得和：每次向右滑一格，只需要增加新格的值，然后减去窗口头的值即可，减少重复计算；\n时间复杂度 由于只需要一次遍历就可以取到窗口格中的数据，所以时间复杂度为数组长度O(n)\n代码 def SlideWindow(nums: List[int], size: int): left = 0, right = 0 while(right  len(nums)): right_num = nums[right]\t# right_num为将要移入窗口的数值 right += 1\t# 右窗口右移 ...\t# 进行窗口内数据的一系列更新 while(window needs shrink):\t# 判断左侧窗口是否要收缩 left_num = nums[left]\t# left_num为将移出窗口的字符 left+= 1\t# 左窗口右移 ...\t# 进行窗口内数据的一系列更新 题目 力扣1984：学生分数的最小差值\n资料 https://labuladong.gitee.io/algo/2/21/60/\n查找\u0026排序 二分查找 定义 数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。\n特点 数组必须是按有序结构的；\n时间复杂度 O(log2n)\n时间复杂度即是while循环的次数。总共n个元素，每次分成2个子数组，每个子数组为n/2, n/4, …, n/2^k，k为循环次数\n由于n/2^k取整后=1，即令n/2^k = 1，求得k = log2n\n代码 def bin_search(data_list, val): low = 0 # 最小数下标  high = len(data_list) - 1 # 最大数下标  while low  high: mid = (low + high) // 2 + low\t# 中间数下标  if data_list[mid] == val: # 如果中间数下标等于val, 返回  return mid elif data_list[mid]  val: # 如果val在中间数左边, 移动high下标  high = mid - 1 else: # 如果val在中间数右边, 移动low下标  low = mid + 1 return None # val不存在, 返回None ret = bin_search(list(range(1, 10)), 3) print(ret) 堆排序 时间复杂度 O(nlog2n)\n空间复杂度 O(1)，对数组原地排序，没有另外开辟空间\ndef heapify(arr, n, i): largest = i l = 2 * i + 1 # left = 2*i + 1  r = 2 * i + 2 # right = 2*i + 2  if l  n and arr[i]  arr[l]: largest = l if r  n and arr[largest]  arr[r]: largest = r if largest != i: arr[i],arr[largest] = arr[largest],arr[i] # 交换 heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build a maxheap.  for i in range(n, -1, -1): heapify(arr, n, i) # 一个个交换元素 for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # 交换 heapify(arr, i, 0) 快速排序 时间复杂度 O(nlog2n)\n空间复杂度 O(nlog2n)\ndef quick_sort(array, left, right): if left = right: return low = left high = right key = array[low] while left  right: while left  right and array[right]  key: right -= 1 array[left] = array[right] # print('right',array) while left  right and array[left]  key: left += 1 array[right] = array[left] # print('left',array) array[right] = key quick_sort(array, low, left - 1) quick_sort(array, left + 1, high) 归并排序 时间复杂度 O(nlog2n)\n空间复杂度 O(n)\ndef merge(arr, l, m, r): n1 = m - l + 1 n2 = r- m # 创建临时数组 L = [0] * (n1) R = [0] * (n2) # 拷贝数据到临时数组 arrays L[] 和 R[]  for i in range(0 , n1): L[i] = arr[l + i] for j in range(0 , n2): R[j] = arr[m + 1 + j] # 归并临时数组到 arr[l..r]  i = 0 # 初始化第一个子数组的索引 j = 0 # 初始化第二个子数组的索引 k = l # 初始归并子数组的索引 while i  n1 and j  n2 : if L[i]  R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # 拷贝 L[] 的保留元素 while i  n1: arr[k] = L[i] i += 1 k += 1 # 拷贝 R[] 的保留元素 while j  n2: arr[k] = R[j] j += 1 k += 1 def mergeSort(arr,l,r): if l  r: m = int((l+(r-1))/2) mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) 图 广度优先搜索(BFS) 也称宽度优先搜索(breadth_first search,bfs)\n定义 是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。\n原理 假设从图中某个顶点v出发，在访问了v之后，依次访问v的各个未曾访问过的邻接点，然后按照访问的顺序，再分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点” 先于 “后被访问的顶点的邻接点” 被访问（即先访问近的点，再访问远的点，有顺序的要求），直至图中所有已被访问的顶点的邻接点都被访问到。若此时还有顶点未被访问（如没有连通在一起的图），则另选图中一个未曾被访问过的顶点作为起始点，重复前述过程，直至图中所有的顶点都被访问到。\n深度优先搜索 (DFS) (depth_first search,dfs)\n定义 简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次\n原理 深度优先搜索是个不断探查和回溯的过程。假设初始状态是图中所有顶点未曾访问，则深度优先搜索可以从图中的某个顶点v开始出发，作为当前顶点。访问此顶点，并设置该顶点的访问标志，接着从v的未被访问的邻接点中找出一个作为下一步探查的当前顶点。若当前顶点的所有邻接点都被访问过，则退回一步，将前一步访问的顶点重新取出，作为当前探查顶点\n动态规划 https://labuladong.gitee.io/algo/3/\n定义 动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。编程中一般形式就是求最值问题\n原理 求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。\n动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。\n三要素  重叠子问题 最优子结构 状态转移方程  # 初始化 base case dp[0][0][...] = base # 进行状态转移 for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 求最值(选择1，选择2...) ",
  "wordCount" : "545",
  "inLanguage": "en",
  "datePublished": "2022-03-06T12:34:17+08:00",
  "dateModified": "2022-03-06T12:34:17+08:00",
  "mainEntityOfPage": {
    "@type": "WebPage",
    "@id": "http://johnhoowong.gitee.io/blog.gitee.io/posts/%E7%AE%97%E6%B3%95/"
  },
  "publisher": {
    "@type": "Organization",
    "name": "Johnhoo's Blog",
    "logo": {
      "@type": "ImageObject",
      "url": "http://johnhoowong.gitee.io/blog.gitee.io/favicon.ico"
    }
  }
}
</script>
</head>

<body class="" id="top">
<script>
    if (localStorage.getItem("pref-theme") === "dark") {
        document.body.classList.add('dark');
    } else if (localStorage.getItem("pref-theme") === "light") {
        document.body.classList.remove('dark')
    } else if (window.matchMedia('(prefers-color-scheme: dark)').matches) {
        document.body.classList.add('dark');
    }

</script>

<header class="header">
    <nav class="nav">
        <div class="logo">
            <a href="http://johnhoowong.gitee.io/blog.gitee.io" accesskey="h" title="Johnhoo&#39;s Blog (Alt + H)">Johnhoo&#39;s Blog</a>
            <span class="logo-switches">
                <button id="theme-toggle" accesskey="t" title="(Alt + T)">
                    <svg id="moon" xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24"
                        fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round"
                        stroke-linejoin="round">
                        <path d="M21 12.79A9 9 0 1 1 11.21 3 7 7 0 0 0 21 12.79z"></path>
                    </svg>
                    <svg id="sun" xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24"
                        fill="none" stroke="currentColor" stroke-width="2" stroke-linecap="round"
                        stroke-linejoin="round">
                        <circle cx="12" cy="12" r="5"></circle>
                        <line x1="12" y1="1" x2="12" y2="3"></line>
                        <line x1="12" y1="21" x2="12" y2="23"></line>
                        <line x1="4.22" y1="4.22" x2="5.64" y2="5.64"></line>
                        <line x1="18.36" y1="18.36" x2="19.78" y2="19.78"></line>
                        <line x1="1" y1="12" x2="3" y2="12"></line>
                        <line x1="21" y1="12" x2="23" y2="12"></line>
                        <line x1="4.22" y1="19.78" x2="5.64" y2="18.36"></line>
                        <line x1="18.36" y1="5.64" x2="19.78" y2="4.22"></line>
                    </svg>
                </button>
            </span>
        </div>
        <ul id="menu">
        </ul>
    </nav>
</header>
<main class="main">

<article class="post-single">
  <header class="post-header">
    
    <h1 class="post-title">
      算法
    </h1>
    <div class="post-meta"><span title='2022-03-06 12:34:17 +0800 CST'>March 6, 2022</span>

</div>
  </header> 
  <div class="post-content"><h1 id="常见算法">常见算法<a hidden class="anchor" aria-hidden="true" href="#常见算法">#</a></h1>
<h1 id="线性表">线性表<a hidden class="anchor" aria-hidden="true" href="#线性表">#</a></h1>
<h2 id="滑动窗口">滑动窗口<a hidden class="anchor" aria-hidden="true" href="#滑动窗口">#</a></h2>
<h3 id="定义">定义<a hidden class="anchor" aria-hidden="true" href="#定义">#</a></h3>
<p>在给定特定窗口大小的数组或字符串上执行要求的操作</p>
<h3 id="示意图">示意图<a hidden class="anchor" aria-hidden="true" href="#示意图">#</a></h3>
<p><img loading="lazy" src="https://gitee.com/johnhoowong/img/raw/master/image-20220306123926259.png" alt="image-20220306123926259"  />
</p>
<h3 id="特点">特点<a hidden class="anchor" aria-hidden="true" href="#特点">#</a></h3>
<p>如果要计算窗口内值得和：每次向右滑一格，只需要增加新格的值，然后减去窗口头的值即可，减少重复计算；</p>
<h3 id="时间复杂度">时间复杂度<a hidden class="anchor" aria-hidden="true" href="#时间复杂度">#</a></h3>
<p>由于只需要一次遍历就可以取到窗口格中的数据，所以时间复杂度为数组长度O(n)</p>
<h3 id="代码">代码<a hidden class="anchor" aria-hidden="true" href="#代码">#</a></h3>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#282a36;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#ff79c6">def</span> <span style="color:#50fa7b">SlideWindow</span>(nums: List[<span style="color:#8be9fd;font-style:italic">int</span>], size: <span style="color:#8be9fd;font-style:italic">int</span>):
    left <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">0</span>, right <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">0</span>
    <span style="color:#ff79c6">while</span>(right <span style="color:#ff79c6">&lt;</span> <span style="color:#8be9fd;font-style:italic">len</span>(nums)):
        right_num <span style="color:#ff79c6">=</span> nums[right]			<span style="color:#6272a4"># right_num为将要移入窗口的数值</span>
        right <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>						<span style="color:#6272a4"># 右窗口右移</span>
        <span style="color:#ff79c6">...</span>								<span style="color:#6272a4"># 进行窗口内数据的一系列更新</span>
        <span style="color:#ff79c6">while</span>(window needs shrink):		<span style="color:#6272a4"># 判断左侧窗口是否要收缩</span>
            left_num <span style="color:#ff79c6">=</span> nums[left]		<span style="color:#6272a4"># left_num为将移出窗口的字符</span>
            left<span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>					<span style="color:#6272a4"># 左窗口右移</span>
            <span style="color:#ff79c6">...</span>							<span style="color:#6272a4"># 进行窗口内数据的一系列更新</span>
</code></pre></div><h3 id="题目">题目<a hidden class="anchor" aria-hidden="true" href="#题目">#</a></h3>
<p><a href="https://leetcode-cn.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores/">力扣1984：学生分数的最小差值</a></p>
<h3 id="资料">资料<a hidden class="anchor" aria-hidden="true" href="#资料">#</a></h3>
<p><a href="https://labuladong.gitee.io/algo/2/21/60/">https://labuladong.gitee.io/algo/2/21/60/</a></p>
<h1 id="查找排序">查找&amp;排序<a hidden class="anchor" aria-hidden="true" href="#查找排序">#</a></h1>
<h2 id="二分查找">二分查找<a hidden class="anchor" aria-hidden="true" href="#二分查找">#</a></h2>
<h3 id="定义-1">定义<a hidden class="anchor" aria-hidden="true" href="#定义-1">#</a></h3>
<p>数组中元素是按升序排列，将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。</p>
<h3 id="特点-1">特点<a hidden class="anchor" aria-hidden="true" href="#特点-1">#</a></h3>
<p>数组必须是按有序结构的；</p>
<h3 id="时间复杂度-1">时间复杂度<a hidden class="anchor" aria-hidden="true" href="#时间复杂度-1">#</a></h3>
<p>O(log2n)</p>
<p>时间复杂度即是while循环的次数。总共n个元素，每次分成2个子数组，每个子数组为n/2, n/4, &hellip;, n/2^k，k为循环次数</p>
<p>由于n/2^k取整后&gt;=1，即令n/2^k = 1，求得k = log2n</p>
<h3 id="代码-1">代码<a hidden class="anchor" aria-hidden="true" href="#代码-1">#</a></h3>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#282a36;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#ff79c6">def</span> <span style="color:#50fa7b">bin_search</span>(data_list, val):    
    low <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">0</span>                         		<span style="color:#6272a4"># 最小数下标    </span>
    high <span style="color:#ff79c6">=</span> <span style="color:#8be9fd;font-style:italic">len</span>(data_list) <span style="color:#ff79c6">-</span> <span style="color:#bd93f9">1</span>       		<span style="color:#6272a4"># 最大数下标    </span>
    <span style="color:#ff79c6">while</span> low <span style="color:#ff79c6">&lt;=</span> high:        
        mid <span style="color:#ff79c6">=</span> (low <span style="color:#ff79c6">+</span> high) <span style="color:#ff79c6">//</span> <span style="color:#bd93f9">2</span> <span style="color:#ff79c6">+</span> low		<span style="color:#6272a4"># 中间数下标        </span>
        <span style="color:#ff79c6">if</span> data_list[mid] <span style="color:#ff79c6">==</span> val:   		<span style="color:#6272a4"># 如果中间数下标等于val, 返回             </span>
            <span style="color:#ff79c6">return</span> mid        
        <span style="color:#ff79c6">elif</span> data_list[mid] <span style="color:#ff79c6">&gt;</span> val:  		<span style="color:#6272a4"># 如果val在中间数左边, 移动high下标            </span>
            high <span style="color:#ff79c6">=</span> mid <span style="color:#ff79c6">-</span> <span style="color:#bd93f9">1</span>        
        <span style="color:#ff79c6">else</span>:                       		<span style="color:#6272a4"># 如果val在中间数右边, 移动low下标            </span>
            low <span style="color:#ff79c6">=</span> mid <span style="color:#ff79c6">+</span> <span style="color:#bd93f9">1</span>    
    <span style="color:#ff79c6">return</span> <span style="color:#ff79c6">None</span>                     		<span style="color:#6272a4"># val不存在, 返回None</span>
ret <span style="color:#ff79c6">=</span> bin_search(<span style="color:#8be9fd;font-style:italic">list</span>(<span style="color:#8be9fd;font-style:italic">range</span>(<span style="color:#bd93f9">1</span>, <span style="color:#bd93f9">10</span>)), <span style="color:#bd93f9">3</span>)
<span style="color:#8be9fd;font-style:italic">print</span>(ret)
</code></pre></div><p><img loading="lazy" src="https://gitee.com/johnhoowong/img/raw/master/849589-20180402133438219-1946132192.png" alt="img"  />
</p>
<h2 id="堆排序">堆排序<a hidden class="anchor" aria-hidden="true" href="#堆排序">#</a></h2>
<h3 id="时间复杂度-2">时间复杂度<a hidden class="anchor" aria-hidden="true" href="#时间复杂度-2">#</a></h3>
<p>O(nlog2n)</p>
<h3 id="空间复杂度">空间复杂度<a hidden class="anchor" aria-hidden="true" href="#空间复杂度">#</a></h3>
<p>O(1)，对数组原地排序，没有另外开辟空间</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#282a36;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#ff79c6">def</span> <span style="color:#50fa7b">heapify</span>(arr, n, i): 
    largest <span style="color:#ff79c6">=</span> i  
    l <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">2</span> <span style="color:#ff79c6">*</span> i <span style="color:#ff79c6">+</span> <span style="color:#bd93f9">1</span>     <span style="color:#6272a4"># left = 2*i + 1 </span>
    r <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">2</span> <span style="color:#ff79c6">*</span> i <span style="color:#ff79c6">+</span> <span style="color:#bd93f9">2</span>     <span style="color:#6272a4"># right = 2*i + 2 </span>
  
    <span style="color:#ff79c6">if</span> l <span style="color:#ff79c6">&lt;</span> n <span style="color:#ff79c6">and</span> arr[i] <span style="color:#ff79c6">&lt;</span> arr[l]: 
        largest <span style="color:#ff79c6">=</span> l 
  
    <span style="color:#ff79c6">if</span> r <span style="color:#ff79c6">&lt;</span> n <span style="color:#ff79c6">and</span> arr[largest] <span style="color:#ff79c6">&lt;</span> arr[r]: 
        largest <span style="color:#ff79c6">=</span> r 
  
    <span style="color:#ff79c6">if</span> largest <span style="color:#ff79c6">!=</span> i: 
        arr[i],arr[largest] <span style="color:#ff79c6">=</span> arr[largest],arr[i]  <span style="color:#6272a4"># 交换</span>
  
        heapify(arr, n, largest) 
  
<span style="color:#ff79c6">def</span> <span style="color:#50fa7b">heapSort</span>(arr): 
    n <span style="color:#ff79c6">=</span> <span style="color:#8be9fd;font-style:italic">len</span>(arr) 
  
    <span style="color:#6272a4"># Build a maxheap. </span>
    <span style="color:#ff79c6">for</span> i <span style="color:#ff79c6">in</span> <span style="color:#8be9fd;font-style:italic">range</span>(n, <span style="color:#ff79c6">-</span><span style="color:#bd93f9">1</span>, <span style="color:#ff79c6">-</span><span style="color:#bd93f9">1</span>): 
        heapify(arr, n, i) 
  
    <span style="color:#6272a4"># 一个个交换元素</span>
    <span style="color:#ff79c6">for</span> i <span style="color:#ff79c6">in</span> <span style="color:#8be9fd;font-style:italic">range</span>(n<span style="color:#ff79c6">-</span><span style="color:#bd93f9">1</span>, <span style="color:#bd93f9">0</span>, <span style="color:#ff79c6">-</span><span style="color:#bd93f9">1</span>): 
        arr[i], arr[<span style="color:#bd93f9">0</span>] <span style="color:#ff79c6">=</span> arr[<span style="color:#bd93f9">0</span>], arr[i]   <span style="color:#6272a4"># 交换</span>
        heapify(arr, i, <span style="color:#bd93f9">0</span>) 
</code></pre></div><h2 id="快速排序">快速排序<a hidden class="anchor" aria-hidden="true" href="#快速排序">#</a></h2>
<h3 id="时间复杂度-3">时间复杂度<a hidden class="anchor" aria-hidden="true" href="#时间复杂度-3">#</a></h3>
<p>O(nlog2n)</p>
<h3 id="空间复杂度-1">空间复杂度<a hidden class="anchor" aria-hidden="true" href="#空间复杂度-1">#</a></h3>
<p>O(nlog2n)</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#282a36;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#ff79c6">def</span> <span style="color:#50fa7b">quick_sort</span>(array, left, right):
    <span style="color:#ff79c6">if</span> left <span style="color:#ff79c6">&gt;=</span> right:
        <span style="color:#ff79c6">return</span>
    low <span style="color:#ff79c6">=</span> left
    high <span style="color:#ff79c6">=</span> right
    key <span style="color:#ff79c6">=</span> array[low]
    <span style="color:#ff79c6">while</span> left <span style="color:#ff79c6">&lt;</span> right:
        <span style="color:#ff79c6">while</span> left <span style="color:#ff79c6">&lt;</span> right <span style="color:#ff79c6">and</span> array[right] <span style="color:#ff79c6">&gt;</span> key:
            right <span style="color:#ff79c6">-=</span> <span style="color:#bd93f9">1</span>
        array[left] <span style="color:#ff79c6">=</span> array[right]
        <span style="color:#6272a4"># print(&#39;right&#39;,array)</span>
        <span style="color:#ff79c6">while</span> left <span style="color:#ff79c6">&lt;</span> right <span style="color:#ff79c6">and</span> array[left] <span style="color:#ff79c6">&lt;=</span> key:
            left <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
        array[right] <span style="color:#ff79c6">=</span> array[left]
        <span style="color:#6272a4"># print(&#39;left&#39;,array)</span>
    array[right] <span style="color:#ff79c6">=</span> key
    quick_sort(array, low, left <span style="color:#ff79c6">-</span> <span style="color:#bd93f9">1</span>)
    quick_sort(array, left <span style="color:#ff79c6">+</span> <span style="color:#bd93f9">1</span>, high)
</code></pre></div><h2 id="归并排序">归并排序<a hidden class="anchor" aria-hidden="true" href="#归并排序">#</a></h2>
<h3 id="时间复杂度-4">时间复杂度<a hidden class="anchor" aria-hidden="true" href="#时间复杂度-4">#</a></h3>
<p>O(nlog2n)</p>
<h3 id="空间复杂度-2">空间复杂度<a hidden class="anchor" aria-hidden="true" href="#空间复杂度-2">#</a></h3>
<p>O(n)</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#282a36;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#ff79c6">def</span> <span style="color:#50fa7b">merge</span>(arr, l, m, r): 
    n1 <span style="color:#ff79c6">=</span> m <span style="color:#ff79c6">-</span> l <span style="color:#ff79c6">+</span> <span style="color:#bd93f9">1</span>
    n2 <span style="color:#ff79c6">=</span> r<span style="color:#ff79c6">-</span> m 
    <span style="color:#6272a4"># 创建临时数组</span>
    L <span style="color:#ff79c6">=</span> [<span style="color:#bd93f9">0</span>] <span style="color:#ff79c6">*</span> (n1)
    R <span style="color:#ff79c6">=</span> [<span style="color:#bd93f9">0</span>] <span style="color:#ff79c6">*</span> (n2)
    <span style="color:#6272a4"># 拷贝数据到临时数组 arrays L[] 和 R[] </span>
    <span style="color:#ff79c6">for</span> i <span style="color:#ff79c6">in</span> <span style="color:#8be9fd;font-style:italic">range</span>(<span style="color:#bd93f9">0</span> , n1): 
        L[i] <span style="color:#ff79c6">=</span> arr[l <span style="color:#ff79c6">+</span> i] 
    <span style="color:#ff79c6">for</span> j <span style="color:#ff79c6">in</span> <span style="color:#8be9fd;font-style:italic">range</span>(<span style="color:#bd93f9">0</span> , n2): 
        R[j] <span style="color:#ff79c6">=</span> arr[m <span style="color:#ff79c6">+</span> <span style="color:#bd93f9">1</span> <span style="color:#ff79c6">+</span> j] 
    <span style="color:#6272a4"># 归并临时数组到 arr[l..r] </span>
    i <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">0</span>     <span style="color:#6272a4"># 初始化第一个子数组的索引</span>
    j <span style="color:#ff79c6">=</span> <span style="color:#bd93f9">0</span>     <span style="color:#6272a4"># 初始化第二个子数组的索引</span>
    k <span style="color:#ff79c6">=</span> l     <span style="color:#6272a4"># 初始归并子数组的索引</span>
    <span style="color:#ff79c6">while</span> i <span style="color:#ff79c6">&lt;</span> n1 <span style="color:#ff79c6">and</span> j <span style="color:#ff79c6">&lt;</span> n2 : 
        <span style="color:#ff79c6">if</span> L[i] <span style="color:#ff79c6">&lt;=</span> R[j]: 
            arr[k] <span style="color:#ff79c6">=</span> L[i] 
            i <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
        <span style="color:#ff79c6">else</span>: 
            arr[k] <span style="color:#ff79c6">=</span> R[j] 
            j <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
        k <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
    <span style="color:#6272a4"># 拷贝 L[] 的保留元素</span>
    <span style="color:#ff79c6">while</span> i <span style="color:#ff79c6">&lt;</span> n1: 
        arr[k] <span style="color:#ff79c6">=</span> L[i] 
        i <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
        k <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
    <span style="color:#6272a4"># 拷贝 R[] 的保留元素</span>
    <span style="color:#ff79c6">while</span> j <span style="color:#ff79c6">&lt;</span> n2: 
        arr[k] <span style="color:#ff79c6">=</span> R[j] 
        j <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
        k <span style="color:#ff79c6">+=</span> <span style="color:#bd93f9">1</span>
<span style="color:#ff79c6">def</span> <span style="color:#50fa7b">mergeSort</span>(arr,l,r): 
    <span style="color:#ff79c6">if</span> l <span style="color:#ff79c6">&lt;</span> r: 
        m <span style="color:#ff79c6">=</span> <span style="color:#8be9fd;font-style:italic">int</span>((l<span style="color:#ff79c6">+</span>(r<span style="color:#ff79c6">-</span><span style="color:#bd93f9">1</span>))<span style="color:#ff79c6">/</span><span style="color:#bd93f9">2</span>)
        mergeSort(arr, l, m) 
        mergeSort(arr, m<span style="color:#ff79c6">+</span><span style="color:#bd93f9">1</span>, r) 
        merge(arr, l, m, r) 
</code></pre></div><h1 id="图">图<a hidden class="anchor" aria-hidden="true" href="#图">#</a></h1>
<h2 id="广度优先搜索bfs">广度优先搜索(BFS)<a hidden class="anchor" aria-hidden="true" href="#广度优先搜索bfs">#</a></h2>
<p>也称宽度优先搜索(breadth_first search,bfs)</p>
<h3 id="定义-2">定义<a hidden class="anchor" aria-hidden="true" href="#定义-2">#</a></h3>
<p>是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。</p>
<h3 id="原理">原理<a hidden class="anchor" aria-hidden="true" href="#原理">#</a></h3>
<p>假设从图中某个顶点v出发，在访问了v之后，<strong>依次访问</strong>v的各个未曾访问过的<strong>邻接点</strong>，然后按照访问的顺序，再分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点” 先于 “后被访问的顶点的邻接点” 被访问（即先访问近的点，再访问远的点，有顺序的要求），直至图中所有已被访问的顶点的邻接点都被访问到。若此时还有顶点未被访问（如没有连通在一起的图），则另选图中一个未曾被访问过的顶点作为起始点，重复前述过程，直至图中所有的顶点都被访问到。</p>
<h2 id="深度优先搜索-dfs">深度优先搜索 (DFS)<a hidden class="anchor" aria-hidden="true" href="#深度优先搜索-dfs">#</a></h2>
<p>(depth_first search,dfs)</p>
<h3 id="定义-3">定义<a hidden class="anchor" aria-hidden="true" href="#定义-3">#</a></h3>
<p>简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次</p>
<h3 id="原理-1">原理<a hidden class="anchor" aria-hidden="true" href="#原理-1">#</a></h3>
<p>深度优先搜索是个不断探查和回溯的过程。假设初始状态是图中所有顶点未曾访问，则深度优先搜索可以从图中的某个顶点v开始出发，作为当前顶点。访问此顶点，并设置该顶点的访问标志，接着从v的未被访问的<strong>邻接点</strong>中找出一个作为下一步探查的当前顶点。若当前顶点的所有邻接点都被访问过，则退回一步，将前一步访问的顶点重新取出，作为当前探查顶点</p>
<h2 id="动态规划">动态规划<a hidden class="anchor" aria-hidden="true" href="#动态规划">#</a></h2>
<p><a href="https://labuladong.gitee.io/algo/3/">https://labuladong.gitee.io/algo/3/</a></p>
<h3 id="定义-4">定义<a hidden class="anchor" aria-hidden="true" href="#定义-4">#</a></h3>
<p>动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。编程中一般形式就是<strong>求最值问题</strong></p>
<h3 id="原理-2">原理<a hidden class="anchor" aria-hidden="true" href="#原理-2">#</a></h3>
<p>求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。</p>
<p>动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。</p>
<h3 id="三要素">三要素<a hidden class="anchor" aria-hidden="true" href="#三要素">#</a></h3>
<ul>
<li>重叠子问题</li>
<li>最优子结构</li>
<li>状态转移方程</li>
</ul>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#282a36;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#6272a4"># 初始化 base case</span>
dp[<span style="color:#bd93f9">0</span>][<span style="color:#bd93f9">0</span>][<span style="color:#ff79c6">...</span>] <span style="color:#ff79c6">=</span> base
<span style="color:#6272a4"># 进行状态转移</span>
<span style="color:#ff79c6">for</span> 状态1 <span style="color:#ff79c6">in</span> 状态1的所有取值：
    <span style="color:#ff79c6">for</span> 状态2 <span style="color:#ff79c6">in</span> 状态2的所有取值：
        <span style="color:#ff79c6">for</span> <span style="color:#ff79c6">...</span>
            dp[状态1][状态2][<span style="color:#ff79c6">...</span>] <span style="color:#ff79c6">=</span> 求最值(选择1，选择2<span style="color:#ff79c6">...</span>)
</code></pre></div>

  </div>

  <footer class="post-footer">
  </footer>
</article>
    </main>
    
<footer class="footer">
    <span>&copy; 2022 <a href="http://johnhoowong.gitee.io/blog.gitee.io">Johnhoo&#39;s Blog</a></span>
    <span>
        Powered by
        <a href="https://gohugo.io/" rel="noopener noreferrer" target="_blank">Hugo</a> &
        <a href="https://git.io/hugopapermod" rel="noopener" target="_blank">PaperMod</a>
    </span>
</footer>
<a href="#top" aria-label="go to top" title="Go to Top (Alt + G)" class="top-link" id="top-link" accesskey="g">
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 12 6" fill="currentColor">
        <path d="M12 6H0l6-6z" />
    </svg>
</a>

<script>
    let menu = document.getElementById('menu')
    if (menu) {
        menu.scrollLeft = localStorage.getItem("menu-scroll-position");
        menu.onscroll = function () {
            localStorage.setItem("menu-scroll-position", menu.scrollLeft);
        }
    }

    document.querySelectorAll('a[href^="#"]').forEach(anchor => {
        anchor.addEventListener("click", function (e) {
            e.preventDefault();
            var id = this.getAttribute("href").substr(1);
            if (!window.matchMedia('(prefers-reduced-motion: reduce)').matches) {
                document.querySelector(`[id='${decodeURIComponent(id)}']`).scrollIntoView({
                    behavior: "smooth"
                });
            } else {
                document.querySelector(`[id='${decodeURIComponent(id)}']`).scrollIntoView();
            }
            if (id === "top") {
                history.replaceState(null, null, " ");
            } else {
                history.pushState(null, null, `#${id}`);
            }
        });
    });

</script>
<script>
    var mybutton = document.getElementById("top-link");
    window.onscroll = function () {
        if (document.body.scrollTop > 800 || document.documentElement.scrollTop > 800) {
            mybutton.style.visibility = "visible";
            mybutton.style.opacity = "1";
        } else {
            mybutton.style.visibility = "hidden";
            mybutton.style.opacity = "0";
        }
    };

</script>
<script>
    document.getElementById("theme-toggle").addEventListener("click", () => {
        if (document.body.className.includes("dark")) {
            document.body.classList.remove('dark');
            localStorage.setItem("pref-theme", 'light');
        } else {
            document.body.classList.add('dark');
            localStorage.setItem("pref-theme", 'dark');
        }
    })

</script>
</body>

</html>
